// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 技巧：
// 01 背包问题：使用滚动数组进行优化，删除横坐标，从右往左填表
// 完全背包问题：使用滚动数组进行优化，删除横坐标，从左往右填表

// 例题 9:
// 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
//
//        请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
//
//        如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
//
//        示例 1：
//
//        输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
//        输出：4
//        解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
//        其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
//        示例 2：
//
//        输入：strs = ["10", "0", "1"], m = 1, n = 1
//        输出：2
//        解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
//
//
//        提示：
//
//        1 <= strs.length <= 600
//        1 <= strs[i].length <= 100
//        strs[i] 仅由 '0' 和 '1' 组成
//        1 <= m, n <= 100

// 解题思路:
// dp[i][j][k] 表示 [0, i] 区间内 0 的个数不超过 j, 1 的个数不超过 k 的最大子集的长度
// 初始化：dp[0][j][k] = 0, 0 <= j <= m, 0 <= k <= n
// 根据最后一个位置的字符串分情况讨论：
// 不选最后一个字符串：dp[i][j][k] = dp[i - 1][j][k]
// 选最后一个字符串：dp[i][j][k] = dp[i - 1][j - a][k - b], a 为最后一个字符串中的 0 的个数， b 为字符串中 1 的数量
// 取两者的最大值

public class FindMaxForm {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len + 1][m + 1][n + 1];

        for(int i = 1; i <= len; i++){
            int tmp = count(strs[i - 1]);
            int l = strs[i - 1].length();
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    dp[i][j][k] = dp[i - 1][j][k];
                    if(j >= tmp && k >= l - tmp){
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - tmp][k - l + tmp] + 1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }

    public int count(String s){
        int ret = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '0') ret++;
        }
        return ret;
    }
}
